package _18_剑指OfferII;

import java.util.*;

public class _030_剑指OfferII插入删除和随机访问都是O1的容器 {

    public static void main(String[] args) {

        _030_剑指OfferII插入删除和随机访问都是O1的容器 v = new _030_剑指OfferII插入删除和随机访问都是O1的容器();

        v.remove(0);
        v.remove(0);
        v.insert(0);
        System.out.println(v.getRandom());
        v.remove(0);
        System.out.println(v.insert(0));

    }

    // map保存元素
    Map<Integer, Integer> mapContainers = new HashMap<>();

    // 数据随机删除元素, 删除元素是和最后一个元素交换位置，而不是真正删除元素
    List<Integer> listContainers = new ArrayList<>();

    Random random = new Random();

    /** Initialize your data structure here. */
    public _030_剑指OfferII插入删除和随机访问都是O1的容器() {

    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        boolean isAdd = mapContainers.containsKey(val);
        if (!isAdd) {
            mapContainers.put(val, listContainers.size());
            listContainers.add(val);
        }
        return !isAdd;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        boolean isExist = mapContainers.containsKey(val);
        if (isExist) {
            int index = mapContainers.get(val);
            int end = listContainers.size() - 1;
            int lastValue = listContainers.get(end);
            listContainers.set(index, lastValue);
            mapContainers.put(lastValue, index);
            listContainers.remove(end);
            mapContainers.remove(val);
        }
        return isExist;
    }

    /** Get a random element from the set. */
    public int getRandom() {
        return listContainers.get(random.nextInt(listContainers.size()));
    }


}
